import java.util.Arrays;

public class Solution416 {
    public boolean canPartition(int[] nums) {
        int sum= Arrays.stream(nums).sum();
        if (sum%2!=0){
            return false;
        }
        sum=sum/2;
        boolean[] f= new boolean[sum + 1];
        f[0]=true;
        for (int i=0;i<nums.length;i++){
            for (int j=sum;j>=nums[i];j--){
                if (f[j-nums[i]]){
                    f[j]=true;
                }
            }
        }
        return f[sum];
    }

    public static void main(String[] args) {
        System.out.println(new Solution416().canPartition(new int[]{1,2,3,5}));
    }
}
